constexpr double sml = 1e-7;
template<typename T, T P>
struct Gauss{

	int n;
	std::vector<std::vector<double>> matADD;
	std::vector<std::vector<int>> matXOR;
	std::vector<std::vector<int>> matMOD;
	std::vector<T> inv;

	Gauss() {}
	Gauss(int n) {
		init(n);
	}

	void init(int n) {
		this->n = n;
		matADD.assign(n + 1, {});
		matXOR.assign(n + 1, {});
		matMOD.assign(n + 1, {});
		inv.resize(P);
	}

	void initinv() {
		inv[1] = 1;
		for(int i = 2; i < P; i++) {
			inv[i] = (T)(P - 1LL * inv[P % i] * (P / i) % P);
		}
	}

	// 加法方程组
	void gaussAdd() {
		for(int i = 0; i < n; i++) {
			int max = i;
			for(int j = 0; j < n; j++) {
				if(j < i && std::abs(matADD[j][j]) >= sml) {
					continue;
				}
				if(std::abs(matADD[j][i]) > std::abs(matADD[max][i])) {
					max = j;
				}
			}
			std::swap(matADD[i], matADD[max]);
			if(std::abs(matADD[i][i]) >= sml) {
				double tmp = matADD[i][i];
				for(int j = i; j < n + 1; j++) {
					matADD[i][j] /= tmp;
				}
				for(int j = 0; j < n; j++) {
					if(i != j) {
						double rate = matADD[j][i] / matADD[i][i];
						for(int k = i; k < n + 1; k++) {
							matADD[j][k] -= matADD[i][k] * tmp;
						} 
					}
				}
			}
		}
	}

	// 异或方程组
	void gaussXor() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(j < i && matXOR[j][j] == 1) {
					continue;
				}
				if(matXOR[j][i] == 1) {
					std::swap(i, j);
					break;
				}
			}
			if(matXOR[i][i] == 1) {
				for(int j = 0; j < n; j++) {
					if(i != j && matXOR[j][i] == 1) {
						for(int k = i; k < n + 1; k++) {
							matXOR[j][k] ^= matXOR[i][k];
						}
					}
				}
			}
		}
	}

	// 同余方程组
	void gaussMod() {
		initinv();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(j < i && matMOD[j][j] != 0) {
					continue;
				}
				if(matMOD[j][i] != 0) {
					std::swap(matMOD[i], matMOD[j]);
					break;
				}
			}
			if(matMOD[i][i] != 0) {
				for(int j = 0; j < n; j++) {
					if(i != j && matMOD[j][i] != 0) {
						int g = std::gcd(matMOD[j][i], matMOD[i][i]);
						int a = matMOD[i][i] / g;
						int b = matMOD[j][i] / g;
						if(j < i && matMOD[j][j] != 0) {
							for(int k = j; k < i; k++) {
								matMOD[j][k] = (matMOD[j][k] * a) % P;
							}
						}
						for(int k = i; k < n + 1; k++) {
							matMOD[j][k] = ((matMOD[j][k] * a - matMOD[i][k] * b) % P + P) % P;
						}
					}

				}
			}
		}

		for(int i = 0; i < n; i++) {
			if(matMOD[i][i] != 0) {
				bool f = false;
				for(int j = i + 1; j < n; j++) {
					if(matMOD[i][j] != 0) {
						f = true;
						break;
					}
				}
				if(!f) {
					matMOD[i][n] = (matMOD[i][n] * inv[matMOD[i][i]]) % P;
					matMOD[i][i] = 1;
				}
			}
		}
	}
};

template<i32 P>
using gauss = Gauss<i32, P>;

constexpr i32 P = 7;
using G = gauss<P>;